package leetcode.code090;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution extends Solution090 {

	List<Integer> t = new ArrayList<>();
	List<List<Integer>> ans = new ArrayList<>();

//	dfs(false, 0, nums);
	@Override
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		Stack<int[]> s = new Stack<>();// index , choose
		List<Integer> temp = new ArrayList<>();
		List<List<Integer>> ans = new ArrayList<>();
		s.add(new int[] { 0, 0 });// index choose
		int level = 0;
		while (!s.isEmpty()) {
			int[] cur = s.peek();
			if (cur[0] == nums.length) {
				ans.add(new ArrayList<>(temp));
				s.pop();
				level--;
			}

			s.push(new int[] { cur[0] + 1, 0 });
			level++;

			cur = s.peek();
			if (cur[1] == 0 && level == cur[0]) {
				temp.add(nums[cur[0]]);
				s.push(new int[] { cur[0] + 1, 1 });
			} else {
				temp.remove(temp.size() - 1);
				s.pop();
			}
//			temp.add(nums[cur[0]]);
//			s.push(new int[] { cur[0] + 1, 1 });
//			temp.remove(temp.size() - 1);
		}
		return ans;
	}

	public void dfs(boolean choosePre, int cur, int[] nums) {
		if (cur == nums.length) {
			ans.add(new ArrayList<>(t));
			return;
		}
		dfs(false, cur + 1, nums);
//		if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
//			return;
//		}
		t.add(nums[cur]);
		dfs(true, cur + 1, nums);
		t.remove(t.size() - 1);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
	}

}
